#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<string>
using namespace std;

//class Solution {
//public:
//    int findSubstringInWraproundString(string s) {
//        int n = s.size();
//        vector<int>dp(n, 1);
//        for (int i = 1; i < n; i++)
//        {
//            if (s[i - 1] + 1 == s[i] || (s[i - 1] == 'z' && s[i] == 'a'))
//                dp[i] += dp[i - 1];
//        }
//        int hash[26] = { 0 };
//        for (int i = 0; i < n; i++)
//        {
//            if (dp[i] > hash[s[i] - 'a'])
//                hash[s[i] - 'a'] = dp[i];
//        }
//        int sum = 0;
//        for (auto& e : hash)
//            sum += e;
//        return sum;
//    }
//};

class Solution {
public:
    int lengthOfLIS(vector<int>& nums)
    {
        int n = nums.size();
        vector<int>dp(n + 1, 1);
        int ret = 1;
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[j] < nums[i])
                    dp[i] = max(dp[j] + 1, dp[i]);
            }
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};
int main()
{
    vector<int>arr = { 4,10,4,2,3,9 };
    int b=Solution().lengthOfLIS(arr);
    printf("%d ",b);
	return 0;
}